User blog:Deedlit11/The slow-growing hierarchy and other hierarchies
You guys are probably familiar with the fast-growing hierarchy: \(F_0 (n) = n+1 \\ F_{\alpha+1} (n) = F_{\alpha}^n (n)\\ F_{\alpha} (n) = F_{\alpha n} (n) \text{ when } \alpha \text{ is a limit ordinal.}\) Here \(\alphan\) stands for the nth ordinal in the fundamental sequence of \(\alpha\), which we assumed has been defined for all ordinals that we will be using. Slightly less well-known is the Hardy hierarchy: \(H_0 (n) = n \\ H_{\alpha+1} (n) = H_{\alpha} (n+1)\\ H_{\alpha} (n) = H_{\alpha n} (n) \text{ when } \alpha \text{ is a limit ordinal.}\) and even less well-known is the slow-growing hierarchy: \(G_0 (n) = 0 \\ G_{\alpha+1} (n) = G_{\alpha} (n) + 1\\ G_{\alpha} (n) = G_{\alpha n} (n) \text{ when } \alpha \text{ is a limit ordinal.}\) FB100Z rediscovered the slow-growing hierarchy while investigating prime blocks for ordinals. At a casual glance, one might think that the Hardy hierarchy and slow-growing hierarchy are somewhat close, while the fast-growing hierarchy is much faster, since the first two both use +1 in their recursive definition while the fast-growing hierarchy takes the nth iterate. But in fact the opposite is true. The fast-growing and Hardy hierarchies are related by: \(F_{\alpha} (n) \approx H_{\omega^{\alpha}} (n) \) with equality for \(\alpha < \varepsilon_0 \). So the Hardy hierarchy "catches up" to the fast-growing hierarchy at all epsilon numbers. The slow-growing hierarchy, however, is much slower: \(G_{\epsilon_0} (n)\) is only about \(F_3(n)\). To reach \(F_{\epsilon_0}(n)\) in the slow-growing hierarchy, you have to go all the way to the Bachmann-Howard ordinal \(\theta (\epsilon_{\Omega+1}, 0) \). The slow-growing hierarchy does in fact eventually catch up to the Hardy and fast-growing hierarchies, at the very large ordinal \(\psi_{\Omega_1}(\Omega_{\omega}) \). So relatively speaking the Hardy hierarchy is much closer in growth rate to the fast-growing hierarchy than the slow-growing hierarchy. So how fast does the slow-growing hierarchy grow? for \(\alpha < \varepsilon_0 \), you can compute \(G_{\alpha} (n) \) by taking the Cantor normal form of \(\alpha\) and replacing each instance of \(\omega\) with \(n\). \(G_{\epsilon_0}(n) = n \uparrow \uparrow n \). After that, analysis becomes difficult due to the complexities of the fundamental sequences. It is known that \(G_{\varphi(\omega, 0)}(n)\) is at the level of the Ackermann function. FB100Z asked an interesting question as to the growth rate of \(G_{\Gamma_0}(n)\). From our previous results, it must be between the Ackermann function and \(F_{\epsilon_0}(n)\). How does it compare to, say, \(F_{\omega^{\omega}}(n)\)? That's an interesting question; I'll have to investigate further. The above values of the slow-growing hierarchy were evaluated using a natural definition of fundamental sequences. Interestingly, Andres Weiermann came up with two natural seeming definitions of fundamental sequences that seem quite close to one another. But, using one definition of fundamental sequences, \(G_{\varepsilon_0}(n)\) catches up to \(F_{\varepsilon_0}(n)\); usnng the other definition, \(G_{\theta (\epsilon_{\Omega+1}, 0)}(n)\) grows slower than \(n \uparrow \uparrow n\) ! So it turns out that the growth rate of the slow-growing hierachy is very sensitive to the definition of fundamental sequences. Are the fast-growing and Hardy hierarchies as fragile? I hope not, but it's worth investigating. Category:Blog posts